/**
 * Course Porject 3, COP5612
 * Fall, 2012
 * Author: Tiejia Zhao, Ze Yu
 * UFID: 
 * 		 Tiejia Zhao, 7943-6872
 * 		 Ze Yu,	9619-8380
 */

/**
 * @author codefish
 */
import scala.actors.Actor
import scala.math
import scala.util.Random
import scala.collection.mutable.HashSet
import scala.actors.TIMEOUT
import scala.collection.immutable.TreeSet

object Constants{
    val idLen = 160	//an id is 160 bits
	val b = 4		//a digit is 4 bits
	val md = java.security.MessageDigest.getInstance("SHA-1")
    val colNum = 1 << b
    val rowNum = (idLen/b).toInt
    val maxCol = 100
    val highDigitMask: Byte = 0xf0.toByte
    val lowDigitMask: Byte = 0x0f.toByte
    val L = 1 << b
    val M = 1 << (b+1)
    //val L = 4 //TODO: FIXME
    //val M = 4 // TODO: FIXME
    val rand = Random
    val anchorNumber = 100
    
    // return -1 if a < b, 0 if a==b, 1 if a > b
    def cmpDist(a:Array[Short], b:Array[Short]): Short = {
        //DO NOT USE THIS
        var i = 0
        while(i < rowNum && a(i) == b(i)) i +=1
        if(i == rowNum) {
            return 0.toShort
        } else if(a(i) < b(i)) {
            return -1.toShort
        }
        else{
            return 1.toShort
        }
    }
    val SimpleIdLen = 19
    val SimpleIdBase = 10
    val mask = "1000000000000000000".toLong

    // return -1 if a is closer to o, 1 if b is closer to o, 0 if they are the same
    def localityCmp(a: Long, b: Long, o: Long): Int ={
        //println("comparing " + a + " with "+b+" dist to " + o)
        if(math.abs(a-o) < math.abs(b-o)) return -1
        if(math.abs(a-o) > math.abs(b-o)) return 1
        return 0
    }
}

object project3 {
	def main(args: Array[String]) = {
        //testId(args(0), args(1))
        //testInsert()
        //testState()
        //anchorJoin
        //allNodeJoin(args(0).toInt)
        //testSimpleId
        //testSimpleNeighborSet
        //testSimpleLeafSet
        //testSimpleRoutingTable
	    //testAnchor
	    //testSearchAll
	    //testJoin(args(0).toInt)
	    anchorJoin()
	    otherNodeJoin(args(0).toInt, args(1).toInt)
	}
	def anchorJoin(){
        Anchors.anchors = Array.fill[SimpleNode](Constants.anchorNumber)(
                new SimpleNode(IdFactory.getHostId(), IdFactory.getRandomLocation()))
        for(i <- Anchors.anchors){
            for(j <- Anchors.anchors){
                if(i != j){
                    i.addAsAnchor(j)
                }
            }
        }
        for(i <- Anchors.anchors){
            i.start
        }
        Thread.sleep(3000)
	}
	def otherNodeJoin(numOfNode: Int, numOfMsg: Int){
        Counter.init(numOfNode, numOfMsg)
        Counter.start
        Counter ! StartJoin
	}
	
	def testJoin(nodeNumber: Int, msgNumber: Int){
	    //anchorNodesStart 
	    /*
	     * Anchors
        val n0 = new SimpleNode("0000000000000000000".toLong, 0)
        val n1 = new SimpleNode("1000000000000000000".toLong, 10)
        val n2 = new SimpleNode("2000000000000000000".toLong, 20)
        val n3 = new SimpleNode("3000000000000000000".toLong, 30)
        val n4 = new SimpleNode("4000000000000000000".toLong, 40)
        val n5 = new SimpleNode("5000000000000000000".toLong, 50)
        val n6 = new SimpleNode("6000000000000000000".toLong, 60)
        val n7 = new SimpleNode("7000000000000000000".toLong, 70)
        val n8 = new SimpleNode("8000000000000000000".toLong, 80)
        val n9 = new SimpleNode("9000000000000000000".toLong, 90)
        val n10 = new SimpleNode("0100000000000000000".toLong, 0)
        val n11 = new SimpleNode("1020000000000000000".toLong, 10)
        val n12 = new SimpleNode("2003000000000000000".toLong, 20)
        val n13 = new SimpleNode("3000400000000000000".toLong, 30)
        val n14 = new SimpleNode("4000050000000000000".toLong, 40)
        val n15 = new SimpleNode("5000006000000000000".toLong, 50)
        val n16 = new SimpleNode("6000000700000000000".toLong, 60)
        val n17 = new SimpleNode("7000000080000000000".toLong, 70)
        val n18 = new SimpleNode("8000000009000000000".toLong, 80)
        val n19 = new SimpleNode("9000000000100000000".toLong, 90)
        */
        
        Anchors.anchors = Array.fill[SimpleNode](20)(null)
        Anchors.anchors(0)	= new SimpleNode("0000000000000000000".toLong, 90)
        Anchors.anchors(1) 	= new SimpleNode("1000000000000000000".toLong, 80)
        Anchors.anchors(2)	= new SimpleNode("2000000000000000000".toLong, 70)
        Anchors.anchors(3)	= new SimpleNode("3000000000000000000".toLong, 60)
        Anchors.anchors(4)	= new SimpleNode("4000000000000000000".toLong, 50)
        Anchors.anchors(5) 	= new SimpleNode("5000000000000000000".toLong, 40)
        Anchors.anchors(6) 	= new SimpleNode("6000000000000000000".toLong, 30)
        Anchors.anchors(7) 	= new SimpleNode("7000000000000000000".toLong, 20)
        Anchors.anchors(8) 	= new SimpleNode("8000000000000000000".toLong, 10)
        Anchors.anchors(9) 	= new SimpleNode("9000000000000000000".toLong, 0)
        Anchors.anchors(10) = new SimpleNode("0100000000000000000".toLong, 90)
        Anchors.anchors(11) = new SimpleNode("1020000000000000000".toLong, 80)
        Anchors.anchors(12) = new SimpleNode("2003000000000000000".toLong, 70)
        Anchors.anchors(13) = new SimpleNode("3000400000000000000".toLong, 60)
        Anchors.anchors(14) = new SimpleNode("4000050000000000000".toLong, 50)
        Anchors.anchors(15) = new SimpleNode("5000006000000000000".toLong, 40)
        Anchors.anchors(16) = new SimpleNode("6000000700000000000".toLong, 30)
        Anchors.anchors(17) = new SimpleNode("7000000080000000000".toLong, 20)
        Anchors.anchors(18) = new SimpleNode("8900000009000000000".toLong, 10)
        Anchors.anchors(19) = new SimpleNode("9000000000100000000".toLong, 0)
        for(i <- Anchors.anchors){
            for(j <- Anchors.anchors){
                if(i != j){
                    i.addAsAnchor(j)
                }
            }
        }
        for(i <- Anchors.anchors){
            i.start
        }
        /*
        for(i <- Anchors.anchors) i.printState
        
        var joiningNode = new SimpleNode("8900000000100000000".toLong, 93)
        joiningNode.start
        val myAnchor = Anchors.getAnchor(joiningNode)
        println("start from " + myAnchor.nodeId.key)
        myAnchor ! JoinMsg(joiningNode,0,false)
        Thread.sleep(1000)
        joiningNode.printState
        */
        
        Counter.init(nodeNumber, msgNumber)
        Counter.start
        Counter ! StartJoin
	}

    // all keys are positive
    class SimpleId(rhs:Long){
        var key = rhs
        def distance(rhs:SimpleId): Long = {
            return math.abs(key-rhs.key).toLong
        }
        def > (rhs:SimpleId): Boolean = {
            return key > rhs.key
        }
        def < (rhs:SimpleId): Boolean = {
            return key < rhs.key
        }
        def == (rhs:SimpleId): Boolean = {
            return key == rhs.key
        }

        def getPrefixLen(rhs:SimpleId): Int = {
            var mask = Constants.mask
            var prefixLen = 0
            while(((key/mask).toInt == (rhs.key/mask).toInt) && prefixLen < Constants.SimpleIdLen){
                prefixLen += 1
                mask = (mask/10).toLong
            }
            return prefixLen
        }
        def getDigitAt(idx:Int): Int = {
            var mask = Constants.mask
            if(idx==0) return (key/mask).toInt 
            for(i<-0 until idx-1){
                mask = (mask/10).toLong
            }
            //println("mask is " + mask)
            return ((key%mask)/(mask/10).toLong).toInt
        }
        override def toString = key.toString
    }

    object Anchors{
        var anchors = Array.fill[SimpleNode](Constants.anchorNumber)(null)
        
        // Choose anchor node according to the geometrical dist
        def getAnchor(node: SimpleNode): SimpleNode = {
            var minDist = Long.MaxValue
            var ret: SimpleNode = null
            for(anchor <- anchors){
                val dist = anchor.getGeoDist(node)
                if(dist < minDist){
                    minDist = dist
                    ret = anchor
                }
            }
            return ret
        }
    }
    
    def testAnchor(){
       anchorNodesStart() 
	   for(i <- 0 until Constants.anchorNumber){
	       println("Node " + Anchors.anchors(i).nodeId.key)
	   }
       println("=======================================================")
	   for(i <- 0 until Constants.anchorNumber){
	       println("Node " + Anchors.anchors(i).nodeId.key + " state: ")
	       println("Neighbors")
		   Anchors.anchors(i).neighborSet.printNeighborTable()
	       println("Leaf")
		   Anchors.anchors(i).leafSet.printLeafSet()
	       println("Routing Table")
		   Anchors.anchors(i).routingTable.printRoutingTable()
	   }
    }
    
    object IdFactory{
        var rand = new Random
        var hostIdSet = new HashSet[Long]()
        def getHostId(): Long = {
            var ret: Long = -1
            do{
                ret = rand.nextLong
                if(ret < 0) ret = -ret
            }while(hostIdSet.add(ret) == false)
            return ret
        }
        def getObjId():Long = {
            var ret: Long = -1
            ret = rand.nextLong
            if(ret < 0) ret = -ret
            return ret
        }
        def getRandomLocation():Long = {
            return rand.nextLong
        }
    }
    def anchorNodesStart(){
        for(i <- 0 until Constants.anchorNumber){
            Anchors.anchors(i) = new SimpleNode(IdFactory.getHostId(),
                    IdFactory.getRandomLocation())
        }
        for(i <- 0 until Constants.anchorNumber){
	        for(j <- 0 until Constants.anchorNumber){
	            if(i != j){
	                Anchors.anchors(i).addAsAnchor(Anchors.anchors(j))
	            }
	        }
        }
        for(anchor <- Anchors.anchors){
            anchor.start
        }
    }
    class SimpleEntry(ref: SimpleNode){
        var key = new SimpleId(ref.nodeId.key)
        var handle = ref
        var position = handle.position

        def getKeyAsLong = key.key
        def getPosition = position
    }
    class SimpleNeighborSet(host: SimpleNode, max: Int) {
        var hostHandle = host
        val hostId = host.nodeId
        val maxSize = max
        var currentSize = 0

        var neighbors = List[SimpleEntry]()

        def putEntry(newEntry: SimpleEntry){
            neighbors = insertEntry(newEntry, neighbors)
            if(currentSize < maxSize){
                currentSize += 1
            } else{
                // insert then remove the largest one
                neighbors = neighbors.tail
            }
        }
        def insertEntry(e : SimpleEntry, lst : List[SimpleEntry]) : List[SimpleEntry] = {
            def insertPrime(xs: List[SimpleEntry]) : List[SimpleEntry] = xs match {
                case Nil => List(e)
                case x :: xs if (Constants.localityCmp(e.getPosition, x.getPosition, hostHandle.position) == 1) => e :: x :: xs
                case x :: xs => x :: insertPrime(xs)               
            }   
            
            return insertPrime(lst)
        }
        def printNeighborTable(){
            for(i <- 0 until currentSize){
                print(neighbors(i).key.toString)
                print(" ")
            }
            println()
        }
        def cloneTo(wanter: SimpleNode): SimpleNeighborSet = {
            var ret = new SimpleNeighborSet(wanter, maxSize)
            for(i <- 0 until currentSize){
                //ret.putEntry(neighbors(currentSize-i-1))
                val next = neighbors(currentSize-i-1)
                ret.putEntry(new SimpleEntry(next.handle))
            }
            return ret
        }
    }
    
    class Message {
        val objectId = new SimpleId(IdFactory.getObjId())
    }

    case class JoinMsg(joiningNodeHandle: SimpleNode, hop: Int, isTerminate: Boolean)
    case class RouteMsg(msg: Message, hop: Int, isTerminate: Boolean)
    case class InitNeighborSet(neighbors: SimpleNeighborSet)
    case class InitLeafSet(leaves: SimpleLeafSet)
    case class InitRoutingTable(row: List[SimpleEntry])
    case class Deliver(hop: Int)
    case class JoinDone()
    case class StartJoin()
    case class StartSendMsg(msgNumber: Int)
    case class ReportHop(hop: Int)
    case class NextMsg()
    case class UpdateEntry(joiningNode: SimpleNode)
    case class Stop()
    
    object Counter extends Actor {
        var cnt = 0
        var expect: Int = 0
        var hopCnt = 0
        var msgCnt = 0
        var msgNumber = 0
        var doneNode = 0
        
        var allNodes = List[SimpleNode]()
        
        def act {
            loop{
                react{
                    case JoinDone =>
                        cnt += 1
                        //println(cnt + " nodes joined")
                        if(cnt < expect) 
                        	nextJoin
                    	else{
                    	    // all join finished, start to send msg
                    	    //println("All joining finished, start send message")
                    	    for(node <- allNodes){
                    	        node ! StartSendMsg(msgNumber)
                    	    }
                    	    /* 
                    	    //FOR TESTING
                    	    for(node <- Anchors.anchors){
                    	        set += node.nodeId.key
                    	    }
                    	    for(node <- allNodes){
                    	        set += node.nodeId.key
                    	    }
                    	    for(node <- set){
                    	        println(node)
                    	    }
                    	    
                    	    Thread.sleep(2000)
                	        allNodes(0) ! StartSendMsg(1)
                    	    //FOR TESTING
                    	    */
                    	}
                    case StartJoin =>
                        nextJoin
                    case ReportHop(hop) => 
                        hopCnt += hop
                        msgCnt += 1
                        //doneNode += 1
                        
                        //for testing
                        //println("avg hop = " + (hopCnt.toDouble/msgCnt))
                        //for testing
                        
                        if(msgCnt == this.expect*this.msgNumber){
	                	    //println("All node finish sending msg")
	                	    //println("total hop = " + hopCnt)
	                	    //println("total msg = " + msgCnt)
	                        println("avg hop = " + (hopCnt.toDouble/msgCnt))
                            for(node <- allNodes){
                                node ! Stop
                            }
                            for(node <- Anchors.anchors){
                                node ! Stop
                            }
                            exit()
                        }
                }
            }
        }
        def nextJoin(){
	        val joiningNode = new SimpleNode(IdFactory.getHostId(), IdFactory.getObjId())
	        allNodes = joiningNode :: allNodes
	        joiningNode.start
	        Anchors.getAnchor(joiningNode) ! JoinMsg(joiningNode,0,false)
        }
        def init(nodeNumber: Int, msgNumber: Int){
            this.expect = nodeNumber
            this.msgNumber = msgNumber
        }
    }
    
    class SimpleNode(id: Long, pos: Long) extends Actor{
        val DEBUG = false
        var nodeId = new SimpleId(id)
        var position = pos
        var stimulator: Periodica = null

        var leafSet = new SimpleLeafSet(this, Constants.L) // TODO FIXME
        var neighborSet = new SimpleNeighborSet(this, Constants.M) // TODO FIXME
        var routingTable = new SimpleRoutingTable(this)
        def addAsAnchor(neighbor: SimpleNode){
            neighborSet.putEntry(new SimpleEntry(neighbor))
            leafSet.putEntry(new SimpleEntry(neighbor))
            routingTable.putEntry(new SimpleEntry(neighbor))
        }
        def copyRoutingTableRow(joiningNodeHandle: SimpleNode){
            val prefix = joiningNodeHandle.nodeId.getPrefixLen(this.nodeId)
            for(i <- 0 until prefix){
                joiningNodeHandle ! InitRoutingTable(routingTable.getRow(i))
            }
        }
        def addRowToTable(row: List[SimpleEntry]){
            for(entry <- row){
                this.routingTable.putEntry(entry)
            }
        }
        def update(joiningNode: SimpleNode){
            addAsAnchor(joiningNode)
        }
        class Periodica(ref: SimpleNode, num: Int) extends Actor{
            val waitTime = 1000
            val master = ref
            val msgNumber = num
            var msgCnt = 0
            var readyToStop = false
            def act{
               loop{
                   reactWithin(waitTime){
                       case TIMEOUT => 
                           master ! NextMsg
                           msgCnt += 1
                           if(msgCnt >= msgNumber){
                               //Counter ! Stop
                               readyToStop = true
                               exit
                           }
                   }
               } 
            }
        }
        def act{
            loop{
                react{
		            case JoinMsg(joiningNodeHandle, hop, isTerminate) => 
		                // TODO: A->Z routing
		                //	- Anyway, copy routing table first
		                //	- If it's A, return neighbor set
		                //	 -- deliver	
		                //	- If it's Z, return leaf set
		                //	 -- else call routeJoin and route this msg to the next hop
		                copyRoutingTableRow(joiningNodeHandle)
		                if(hop == 0){
		                    joiningNodeHandle ! InitNeighborSet(neighborSet.cloneTo(joiningNodeHandle))
		                }
		                if(isTerminate == true){
		                    joiningNodeHandle ! InitLeafSet(leafSet.cloneTo(joiningNodeHandle))
		                    joiningNodeHandle ! Deliver(hop)
		                } else{
		                    routeJoin(JoinMsg(joiningNodeHandle, hop, isTerminate))
		                }
		                //update(joiningNodeHandle)
		                
		            case RouteMsg(msg, hop, isTerminate) => 
		                if(isTerminate == true){
		                    Counter ! ReportHop(hop)
		                } else{
		                    routeMessage(RouteMsg(msg, hop, isTerminate))
		                }
		                
		            case InitNeighborSet(neighbors) =>
		                //println("node " + this.nodeId.key + " rec nb set")
		                this.neighborSet = neighbors
		                
		            case InitLeafSet(leaves) =>
		                //println("node " + this.nodeId.key + " rec leaf set")
		                this.leafSet = leaves
		                
		            case InitRoutingTable(row) =>
		                //println("node " + this.nodeId.key + " rec routing table row")
		                addRowToTable(row)
		                
		            case Deliver(hop) =>
		                updateAll()
		                Counter ! JoinDone
		            
		            case StartSendMsg(msgNumber) =>
		                stimulator = new Periodica(this, msgNumber)
		                stimulator.start
		                
		            case NextMsg =>
		                this ! RouteMsg(new Message(), 0, false)
		                
		            case UpdateEntry(joiningNode) =>
		                addAsAnchor(joiningNode)
		                
		            case Stop => 
		                exit
                }
            }
        }
        
        def updateAll(){
            for(i <- neighborSet.neighbors){
                i.handle ! UpdateEntry(this)
            }
            for(i <- leafSet.largerEntries){
                i.handle ! UpdateEntry(this)
            }
            for(i <- leafSet.smallerEntries){
                i.handle ! UpdateEntry(this)
            }
            for(row <- routingTable.routingTable){
                for(j <- row){
                    if(j != null){
                        j.handle ! UpdateEntry(this)
                    }
                }
            }
        }
        
        def routeMessage(msg: RouteMsg){
            val objId = msg.msg.objectId
            if(leafSet.isWithinLeafRange(objId)){
                // within leaf range
                val nearestNode = leafSet.getNearestNode(objId)
                if(DEBUG == true)
	                println("node " + nodeId.key + " forwards " + objId.key + " to " + nearestNode.nodeId.key + " using leaf set")
                //nearestNode ! JoinMsg(joinMsg.joiningNodeHandle, joinMsg.hop+1, true)
                nearestNode ! RouteMsg(msg.msg,msg.hop+1,true)
                
            } else{
                // use the routing table
                val nextHop = routingTable.getNextHop(objId) 
                if(nextHop != null){
                    // forward to the next hop
	                if(DEBUG == true)
		                println("node " + nodeId.key + " forwards " + objId.key + " to " + nextHop.nodeId.key + " using routing table")
	                //nextHop ! JoinMsg(joinMsg.joiningNodeHandle, joinMsg.hop+1, false)
	                nextHop ! RouteMsg(msg.msg, msg.hop+1, false)
                } else{
                    // No next hop is found, search for all the known node
                    val result = searchAll(msg.msg.objectId)
                    if(result != null){
		                if(DEBUG == true)
			                println("node " + nodeId.key + " forwards " + objId.key + " to " + result.nodeId.key + " using all known nodes")
	                    //result ! JoinMsg(joinMsg.joiningNodeHandle, joinMsg.hop+1, false)
	                    result ! RouteMsg(msg.msg, msg.hop+1, false)
                    }else {
                        // add obj to this leaf
	                    Counter ! ReportHop(msg.hop)
                    }
                }
            }
        }
        
        def routeJoin(joinMsg: JoinMsg){
            val joiningNodeId = joinMsg.joiningNodeHandle.nodeId
            if(leafSet.isWithinLeafRange(joiningNodeId)){
                // within leaf range
                val nearestNode = leafSet.getNearestNode(joiningNodeId)
	            //println("node " + nodeId.key + " forwards " + joiningNodeId.key + " to " + nearestNode.nodeId.key + " using leaf set")
                nearestNode ! JoinMsg(joinMsg.joiningNodeHandle, joinMsg.hop+1, true)
                
            } else{
                // use the routing table
                val nextHop = routingTable.getNextHop(joiningNodeId) 
                if(nextHop != null){
                    // forward to the next hop
		            //println("node " + nodeId.key + " forwards " + joiningNodeId.key + " to " + nextHop.nodeId.key + " using routing table")
	                nextHop ! JoinMsg(joinMsg.joiningNodeHandle, joinMsg.hop+1, false)
                } else{
                    // No next hop is found, search for all the known node
                    val result = searchAll(joinMsg.joiningNodeHandle.nodeId)
                    if(result != null){
			            //println("node " + nodeId.key + " forwards " + joiningNodeId.key + " to " + result.nodeId.key + " using all known nodes")
	                    result ! JoinMsg(joinMsg.joiningNodeHandle, joinMsg.hop+1, false)
                    }else {
                        //join this node as leaf
	                    joinMsg.joiningNodeHandle ! InitLeafSet(leafSet.cloneTo(joinMsg.joiningNodeHandle))
	                    joinMsg.joiningNodeHandle ! Deliver(joinMsg.hop)
                    }
                }
            }
        }
        //////////////////////////////////////////////////
        //				TODO: CODE REVIEW
        //////////////////////////////////////////////////
        def searchAll(joiningNodeId: SimpleId): SimpleNode = {
            var ret = List[SimpleNode]()
	        var hostIdSet = new HashSet[Long]()
	        val minPrefixLen = this.nodeId.getPrefixLen(joiningNodeId)
	        val hostDistFromJoiningNode = joiningNodeId.distance(this.nodeId)
	        
	        for(nextCandidate <- leafSet.largerEntries){
	            // avoid duplicate
	            if(joiningNodeId.getPrefixLen(nextCandidate.key) >= minPrefixLen){
		            if(hostIdSet.add(nextCandidate.getKeyAsLong) == true){
		                if(joiningNodeId.distance(nextCandidate.key) < hostDistFromJoiningNode){
		                    ret = nextCandidate.handle :: ret
		                }
		            }
	            }
	        }
	        for(nextCandidate <- leafSet.smallerEntries){
	            // avoid duplicate
	            if(joiningNodeId.getPrefixLen(nextCandidate.key) >= minPrefixLen){
		            if(hostIdSet.add(nextCandidate.getKeyAsLong) == true){
		                if(joiningNodeId.distance(nextCandidate.key) < hostDistFromJoiningNode){
		                    ret = nextCandidate.handle :: ret
		                }
		            }
	            }
	        }
	        for(nextCandidate <- neighborSet.neighbors){
	            // avoid duplicate
	            if(joiningNodeId.getPrefixLen(nextCandidate.key) >= minPrefixLen){
		            if(hostIdSet.add(nextCandidate.getKeyAsLong) == true){
		                if(joiningNodeId.distance(nextCandidate.key) < hostDistFromJoiningNode){
		                    ret = nextCandidate.handle :: ret
		                }
		            }
	            }
	        }
            for (row <- routingTable.routingTable) {
                for (entry <- row) {
                    if (entry != null && hostIdSet.add(entry.getKeyAsLong) == true) {
                        if (joiningNodeId.getPrefixLen(entry.key) >= minPrefixLen) {
                            if (joiningNodeId.distance(entry.key) < hostDistFromJoiningNode) {
                                ret = entry.handle :: ret
                            }
                        }
                    }
                }
            }
	        
            if(ret.isEmpty) return null
            var min = Long.MaxValue
            var winner: SimpleNode = null
            for(item <- ret){
                val myDist = item.nodeId.distance(joiningNodeId)
                if(myDist < min){
                    min = myDist
                    winner = item
                }
            }
            return winner
        }//searchAll
        def getGeoDist(rhs: SimpleNode): Long = {
            return math.abs(rhs.position - this.position).toLong
        }
        def printState(){
            println("State of node " + this.nodeId.key)
            leafSet.printLeafSet
            neighborSet.printNeighborTable
            routingTable.printRoutingTable
        }
    }//SimpleNode

    class SimpleRoutingTable(host: SimpleNode){
        val routingTable = Array.fill
        [Array[SimpleEntry]](Constants.SimpleIdLen)(Array.fill(Constants.SimpleIdBase)(null))

        val hostHandle = host
        val hostId = hostHandle.nodeId

        def putEntry(newNodeEntry: SimpleEntry){
            //println(hostHandle.nodeId.key + " is putting routing table entry " + newNodeEntry.key)
            val entryKey = newNodeEntry.key
            val row = hostId.getPrefixLen(entryKey)
            val col = entryKey.getDigitAt(row)
            if(routingTable(row)(col) == null){
            	routingTable(row)(col) = new SimpleEntry(newNodeEntry.handle)
            } else {
                // Test the current entry, if it's geometrically further to
                // the current node than the new node, we replace it
                val dist = Constants.localityCmp(
                        routingTable(row)(col).position, 
                        newNodeEntry.position, 
                        hostHandle.position)
                if(dist == 1){
	            	routingTable(row)(col) = new SimpleEntry(newNodeEntry.handle)
                }
            }
        }

        def getNextHop(key: SimpleId): SimpleNode = {
            val prefix = hostId.getPrefixLen(key)
            val digit = key.getDigitAt(prefix)
            val ret = routingTable(prefix)(digit)
            if(ret != null){
                return ret.handle
            } else return null
            
        }
        
        // just get this row, no need to re-arrange
        def getRow(rowNumber: Int): List[SimpleEntry] = {
            assert(rowNumber < Constants.SimpleIdLen, {println("get row out of index")})
            var ret = List[SimpleEntry]()
            for(i <- routingTable(rowNumber)){
                if(i != null)
                    ret = new SimpleEntry(i.handle) :: ret
            }
            return ret
        }
        
        def printRoutingTable(){
            println("RoutingTable of node: " + hostId.toString())
            for(i <- 0 until Constants.SimpleIdLen){
                for(j <- 0 until Constants.SimpleIdBase){
                    if(routingTable(i)(j) == null) print("-------------------")
                    else print("%019d".format(routingTable(i)(j).getKeyAsLong))
                    print(" ")
                }
                println
            }
        }
    }
    
    def testSimpleRoutingTable(){
        val n0 = new SimpleNode("5554444444444444445".toLong, 50)
        val n1 = new SimpleNode("5554424444444444441".toLong, 48)
        val n2 = new SimpleNode("5554434444444444442".toLong, 46)
        val n3 = new SimpleNode("5554454444444444443".toLong, 44)
        val n4 = new SimpleNode("5554464444444444444".toLong, 42)
        val n6 = new SimpleNode("5554474444444444446".toLong, 40)
        val n7 = new SimpleNode("5554484444444444447".toLong, 38)
        val n8 = new SimpleNode("5554494444444444448".toLong, 36)
        val n9 = new SimpleNode("5554404444444444449".toLong, 34)
        val n5 = new SimpleNode("5012345678912312357".toLong, 40)
        
        n0.routingTable.putEntry(new SimpleEntry(n1))
        n0.routingTable.putEntry(new SimpleEntry(n2))
        n0.routingTable.putEntry(new SimpleEntry(n3))
        n0.routingTable.putEntry(new SimpleEntry(n4))
        n0.routingTable.putEntry(new SimpleEntry(n5))
        n0.routingTable.putEntry(new SimpleEntry(n6))
        n0.routingTable.putEntry(new SimpleEntry(n7))
        n0.routingTable.putEntry(new SimpleEntry(n8))
        n0.routingTable.putEntry(new SimpleEntry(n9))
        
        n0.routingTable.printRoutingTable
        
        val m0 = new SimpleNode("5011111111111111111".toLong, 39)
        val m1 = new SimpleNode("5022222222222222222".toLong, 41)
        n0.routingTable.putEntry(new SimpleEntry(m0))//doing nothing
        n0.routingTable.printRoutingTable
        n0.routingTable.putEntry(new SimpleEntry(m1))//replace
        n0.routingTable.printRoutingTable
        
        var next = n0.routingTable.getNextHop(new SimpleId("5554498844444444446".toLong))//
        if(next == null) println("null")
        else println(next.nodeId.key)
        next = n0.routingTable.getNextHop(new SimpleId("5034498844444444446".toLong))//
        if(next == null) println("null")
        else println(next.nodeId.key)
        next = n0.routingTable.getNextHop(new SimpleId("5134498844444444446".toLong))//
        if(next == null) println("null")
        else println(next.nodeId.key)
    }

    def testSimpleNeighborSet(){
        var n1 = new SimpleNode(10, 100)
        var n2 = new SimpleNode(11, 10000)
        var n3 = new SimpleNode(12, 200)
        var n4 = new SimpleNode(13, 500)
        var n5 = new SimpleNode(14, 400)
        var n6 = new SimpleNode(15, 600)
        var n7 = new SimpleNode(16, 101)

        var e2 = new SimpleEntry(n2)
        var e3 = new SimpleEntry(n3)
        var e4 = new SimpleEntry(n4)
        var e5 = new SimpleEntry(n5)
        var e6 = new SimpleEntry(n6)
        var e7 = new SimpleEntry(n7)
        n1.neighborSet.putEntry(e2)
        n1.neighborSet.putEntry(e3)
        n1.neighborSet.putEntry(e4)
        n1.neighborSet.printNeighborTable // 11 13 12
        n1.neighborSet.putEntry(e5)
        n1.neighborSet.printNeighborTable // 13 14 12
        n1.neighborSet.putEntry(e6)
        n1.neighborSet.printNeighborTable // 13 14 12
        n1.neighborSet.putEntry(e7)
        n1.neighborSet.printNeighborTable // 14  12 16

        var rec = new SimpleNode(80, 299)// 16 14 12
        n1.neighborSet.cloneTo(rec).printNeighborTable
    }

    class SimpleLeafSet(host: SimpleNode, max: Int) {
        val hostId = host.nodeId
        val hostHandle = host
        val maxSize = (max/2).toInt
        var currentLargerSize = 0
        var currentSmallerSize = 0

        var largerEntries = List[SimpleEntry]() 
        var smallerEntries = List[SimpleEntry]()

        def putEntry(newEntry: SimpleEntry){
            if(newEntry.key > hostId){
                putIntoLargerSet(newEntry)
            }
            if(newEntry.key < hostId){
                putIntoSmallerSet(newEntry)
            }
        }

        def putIntoLargerSet(newEntry: SimpleEntry){
            largerEntries = insertEntry(newEntry, largerEntries)
            if(currentLargerSize < maxSize){
                currentLargerSize += 1
            } else{
                // insert then remove the largest one
                largerEntries = largerEntries.tail
            }
        }
        def putIntoSmallerSet(newEntry: SimpleEntry){
            smallerEntries = insertEntry(newEntry, smallerEntries)
            if(currentSmallerSize < maxSize){
                currentSmallerSize += 1
            } else{
                // insert then remove the largest one
                smallerEntries = smallerEntries.tail
            }
        }
        def insertEntry(e : SimpleEntry, lst : List[SimpleEntry]) : List[SimpleEntry] = {
            def insertPrime(xs: List[SimpleEntry]) : List[SimpleEntry] = xs match {
                case Nil => List(e)
                case x :: xs if (e.key.distance(hostId) > x.key.distance(hostId) ) => e :: x :: xs 
                case x :: xs => x :: insertPrime(xs)               
            }   
            return insertPrime(lst)
        }

        def cloneTo(wanter: SimpleNode): SimpleLeafSet = {
            val ret = new SimpleLeafSet(wanter, maxSize*2)
            for(i <- 0 until currentLargerSize){
                val next = largerEntries(currentLargerSize-i-1)
                ret.putEntry(new SimpleEntry(next.handle))
            }
            for(i <- 0 until currentSmallerSize){
                val next = smallerEntries(currentSmallerSize-i-1)
                ret.putEntry(new SimpleEntry(next.handle))
            }
            ret.putEntry(new SimpleEntry(hostHandle))
            return ret
        }

        def isWithinLeafRange(objectId: SimpleId): Boolean = {
            if((objectId > hostId && maxSize > currentLargerSize) ||
                    (objectId < hostId && maxSize > currentSmallerSize)
            ) return true
            return getMinId() < objectId.key && objectId.key < getMaxId()
        }
        
        def getMaxId(): Long = {
            if(largerEntries.length != 0){
                return largerEntries(0).getKeyAsLong
            } else if(smallerEntries.length != 0){
                return smallerEntries(currentSmallerSize-1).getKeyAsLong
            }
            return Long.MaxValue
        } 
        def getMinId(): Long = {
            if(smallerEntries.length != 0){
                return smallerEntries(0).getKeyAsLong
            } else if(largerEntries.length != 0){
                return largerEntries(currentLargerSize-1).getKeyAsLong
            }
            return Long.MinValue
        } 
        
        def getNearestNode(objectId: SimpleId): SimpleNode = {
            var minDist = Long.MaxValue
            var ret: SimpleNode = null
            for(i <- 0 until currentLargerSize){
                val nextDist = largerEntries(i).key.distance(objectId) 
                if(nextDist < minDist){
                    minDist = nextDist
                    ret = largerEntries(i).handle
                }
            }
            for(i <- 0 until currentSmallerSize){
                val nextDist = smallerEntries(i).key.distance(objectId) 
                if(nextDist < minDist){
                    minDist = nextDist
                    ret = smallerEntries(i).handle
                }
            }
            return ret
        }
        
        def printLeafSet(){
            print("Large: ")
            largerEntries.foreach(x=>print(x.key.toString + " "))
            println
            print("Small: ")
            smallerEntries.foreach(x=>print(x.key.toString + " "))
            println
        }
    }

    def testSimpleLeafSet(){
        val n0 = new SimpleNode(5555, 1)

        val n1 = new SimpleNode(9999, 1)
        val n2 = new SimpleNode(6666, 1)
        val n3 = new SimpleNode(4444, 1)
        val n4 = new SimpleNode(2222, 1)

        val e1 = new SimpleEntry(n1)
        val e2 = new SimpleEntry(n2)
        val e3 = new SimpleEntry(n3)
        val e4 = new SimpleEntry(n4)
        
        n0.leafSet.putEntry(e1)
        n0.leafSet.putEntry(e2)
        n0.leafSet.putEntry(e3)
        n0.leafSet.putEntry(e4)

        n0.leafSet.printLeafSet // 9999 6666 | 2222 4444 

        val n5 = new SimpleNode(6665, 2)
        val n6 = new SimpleNode(2223, 2)

        val e5 = new SimpleEntry(n5)
        val e6 = new SimpleEntry(n6)

        n0.leafSet.putEntry(e5)
        n0.leafSet.putEntry(e6)

        n0.leafSet.printLeafSet // 6666 6665 | 2223 4444 

        val n00 = new SimpleNode(2250, 3)
        n00.leafSet = n0.leafSet.cloneTo(n00)
        n00.leafSet.printLeafSet // 5555 4444 | 2223 
    }

    def testSimpleId(){
        var x = new SimpleId(1.toLong)
        var y = new SimpleId("4611686018427387900".toLong)
        var m = new SimpleId("4611686018427387908".toLong)
        var n = new SimpleId("9223372036854775805".toLong)

        println(x.distance(y))
        println(x.distance(m))
        println(x.distance(n))

        println(y.getPrefixLen(m))
        println(y.getPrefixLen(n))
        println(x.getPrefixLen(n))

        m = new SimpleId("87908".toLong)
        n = new SimpleId("875805".toLong)
        println(m.getPrefixLen(n))
        m = new SimpleId("87908".toLong)
        n = new SimpleId("87805".toLong)
        println(m.getPrefixLen(n))

        println(x.getDigitAt(18))
        println(y.getDigitAt(18))
        println(y.getDigitAt(8))
    }
    def testSearchAll(){
        val n0 = new SimpleNode(10000, 1)

        val n1 = new SimpleNode(11000, 1)
        val n2 = new SimpleNode(9900, 1)
        val n3 = new SimpleNode(12000, 1)
        val n4 = new SimpleNode(9800, 1)
        
        n0.addAsAnchor(n1)
        n0.addAsAnchor(n2)
        n0.addAsAnchor(n3)
        n0.addAsAnchor(n4)
        
        val m1 = new SimpleNode(10050, 1)
        val m2 = new SimpleNode(10499, 1)
        val m3 = new SimpleNode(10501, 1)
        val m4 = new SimpleNode(11499, 1)
        val m5 = new SimpleNode(11501, 1)
        val m6 = new SimpleNode(9851, 1)
        val m7 = new SimpleNode(9700, 1)
        
        var res = n0.searchAll(m1.nodeId)// no winner
        if(res != null) println(res.nodeId.key)
        else println("null")
        
        res = n0.searchAll(m2.nodeId)// no winner
        if(res != null) println(res.nodeId.key)
        else println("null")
        
        res = n0.searchAll(m3.nodeId)// n1 is winner
        if(res != null) println(res.nodeId.key)
        else println("null")
        
        res = n0.searchAll(m4.nodeId)// n1 is winner
        if(res != null) println(res.nodeId.key)
        else println("null")
        
        res = n0.searchAll(m5.nodeId)// n3 is winner
        if(res != null) println(res.nodeId.key)
        else println("null")
        
        res = n0.searchAll(m6.nodeId)// n2 is winner
        if(res != null) println(res.nodeId.key)
        else println("null")
        
        res = n0.searchAll(m7.nodeId)// n4 is winner
        if(res != null) println(res.nodeId.key)
        else println("null")
    }
}
